package  main.java.leetcode.editor.cn;
//2022-04-04 14:41:08
//给你一个数组 nums ，请你完成两类查询。 
//
// 
// 其中一类查询要求 更新 数组 nums 下标对应的值 
// 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right 
// 
//
// 实现 NumArray 类： 
//
// 
// NumArray(int[] nums) 用整数数组 nums 初始化对象 
// void update(int index, int val) 将 nums[index] 的值 更新 为 val 
// int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元
//素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]） 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：
//["NumArray", "sumRange", "update", "sumRange"]
//[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
//输出：
//[null, 9, null, 8]
//
//解释：
//NumArray numArray = new NumArray([1, 3, 5]);
//numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
//numArray.update(1, 2);   // nums = [1,2,5]
//numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 3 * 104 
// -100 <= nums[i] <= 100 
// 0 <= index < nums.length 
// -100 <= val <= 100 
// 0 <= left <= right < nums.length 
// 调用 update 和 sumRange 方法次数不大于 3 * 104 
// 
// Related Topics 设计 树状数组 线段树 数组 
// 👍 414 👎 0

class RangeSumQueryMutable {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        int arr[] = {0,9,5,7,3};
        NumArray solution = new RangeSumQueryMutable().new NumArray(arr);
        int[] att =  solution.sum;
        for (int a: att) {
            System.out.print(a+" ");
        }
        System.out.println();
        System.out.println(solution.sumRange(4, 4));
        System.out.println(solution.sumRange(2, 4));
        System.out.println(solution.sumRange(3, 3));
        solution.update(4,5);
        solution.update(1,7);
        solution.update(0,8);
//        solution.update(1,2);
//        for (int a: att) {
//            System.out.print(a+" ");
//        }
//        System.out.println();
//        System.out.println(solution.sumRange(0, 2));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class NumArray {
    int[] sum;
    int size;
    int[] arr;
    public NumArray(int[] nums) {
        arr = nums;
        int n = nums.length;
        size = (int) Math.sqrt(n);
        sum = new int[(n + size - 1) / size]; // n/size 向上取整
        for (int i = 0; i < n; i++) {
            sum[i / size] += nums[i];
        }
    }
    public void update(int index, int val) {
        sum[index/size] = sum[index/size] - arr[index] + val;
        arr[index] = val;
    }
    public int sumRange(int left, int right) {
        int resultSum = 0;
        int cd1 = left/size;  //确定分块的开始位置
        int cd2 = right/size;  //确定分块的结束位置
        if(cd1 == cd2){  //分块在同一个区域
            while (left<=right){
                resultSum += arr[left];
                left++;
            }
            return resultSum;
        }
        for(int i = cd1;i<cd2;i++){
            resultSum += sum[i];
        }
        //减去非分块区域的数
            //处理分块cd1区
        for(int i = cd1*size;i<left;i++){
            resultSum -= arr[i];
        }
            //处理分块cd2区
        for(int i = cd2*size;i<=right;i++){
            resultSum += arr[i];
        }
        return resultSum;
    }
}
/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(index,val);
 * int param_2 = obj.sumRange(left,right);
 */
//leetcode submit region end(Prohibit modification and deletion)

}
